package object;

public class MyHashMap {
    static class Node {

        public int key;
        public int value;
        public Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    //数组大小最好是素数
    private Node[] arr = new Node[1001];
    //有效元素的个数
    private int size;
    //哈希函数
    public int hashCode(int key) {
        return key % arr.length;
    }
    public void put (int key,int value) {
        int index = hashCode(key);
        for (Node cur = arr[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
        }
        //接下来是进行头插,先让创建的节点指向现在链表当中的头结点
        //再让新创建的节点成为新的头结点,此时该节点就指向原来节点(可能为空)
        //完成头插
        Node newNode = new Node(key,value);
        newNode.next = arr[index];
        arr[index] = newNode;
        size++;
        if ((double)size / arr.length > 0.75) {
            revize();
        }
    }
    private void revize() {
        Node[] newArr = new Node[arr.length << 2];
        for (int i = 0; i < newArr.length; i++) {
            for (Node cur = arr[i]; cur != null; cur = cur.next) {
                Node newNode = new Node(cur.key,cur.value);
                int newIndex = cur.key / newArr.length;
                //理解这个代码的核心就是：引用保存的是地址
                //和上面一样,进行头插操作
                newNode.next = newArr[newIndex];
                newArr[newIndex] = newNode;
            }
        }
        arr = newArr;
    }

    public Integer get (int key) {
        int index = hashCode(key);
        for (Node cur = arr[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                return cur.value;
            }
        }
        return null;
    }

    public void remove (int key) {
        int index = hashCode(key);
        if (arr[index] == null) {
            return;
        }
        if (arr[index].key == key) {
            arr[index] = arr[index].next;
            size--;
            return;
        }
        Node prev = arr[index];
        Node cur = arr[index].next;
        while (cur != null) {
            if (cur.key == key) {
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    public static void main(String[] args) {
        MyHashMap myHashMap = new MyHashMap();


    }

}
